package algorithmTopics.dynamic;

import javax.naming.ldap.spi.LdapDnsProvider;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    //爬楼梯问题,一次走两步，或者一步,一共有多少种方法到达
    public int climbStairs(int n) {
        if (n <= 1) {

            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }


    // 买卖股票的最佳时机
    // 方法一：暴力穷举
//    public int maxProfit(int[] prices) {
//        int res = 0;
//        for (int i = 0; i < prices.length - 1; i++) {
//            int small = prices[i];
//            for (int j = i + 1; j < prices.length; j++) {
//                res = res > (prices[j] - small) ? res : (prices[j] - small);
//            }
//        }
//
//
//        return res;
//
//    }
    // 方法二 遍历一次 最小的值
    public int maxProfit(int[] prices) {
        int res = 0;
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            res = Math.max(prices[i] - min , res);
        }
        return res;
    }

    // 求最大子序列和
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int res = nums[0];
        // 当前下标之前的数最大之和
        int curr = nums[0];
        for (int i = 1; i < len; i++) {
            curr = Math.max(curr, 0) + nums[i];
            res = Math.max(curr, res);
        }
        return res;


    }

    public int rob(int[] nums) {
        //边界条件判断
        if (nums == null || nums.length == 0) {

            return 0;
        }
        int length = nums.length;
        int dp0 = 0;//第1家没偷
        int dp1 = nums[0];//第1家偷了
        //从第2个开始判断
        for (int i = 1; i < length; i++) {
            //防止dp0被修改之后对下面运算造成影响，这里
            //使用一个临时变量temp先把结果存起来，计算完
            //之后再赋值给dp0.
            int temp = Math.max(dp0, dp1);
            dp1 = dp0 + nums[i];
            dp0 = temp;
        }
        //最后取最大值即可
        return Math.max(dp0, dp1);
    }


    //打家劫舍 不能同时偷取相邻的两家 问最大的窃取金额
//    public int rob(int[] nums) {
//        int len = nums.length;
//        int[] res = new int[4];
//        if (len == 1) {
//            return nums[0];
//        }
//        // 从左到右 算出最大的窃取金额
//        for (int i = 0; i < len; i++) {
//            // 当前的金额
//            int curr = nums[i];
//            // 前一个
//            int one = i - 2;
//            //前俩个
//            int two = i - 3;
//            // 前两家都有金额
//            if ( one >= 0 && two >= 0) {
//                // 当前的窃取的最大金额
//                curr += res[one%4] > res[two%4] ? res[one%4] : res[two%4];
//            }else if ( one >= 0) {
//                curr += res[one%4];
//            }
//            //当前节点 最大值添加进去
//            res[i%4] = curr;
//
//        }
//        int data = res[0];
//        for (int i = 1; i < res.length; i++) {
//            if (res[i] > data) {
//                data = res[i];
//            }
//        }
//        return data;
//    }


}
